This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

0
votes
2answers
13 views

Combinations of $6$-digit natural numbers

In each of the following 6-digit natural numbers: $333333,225522,118818,707099$, every digit in the number appears at least twice. Find the number of such 6-digit natural numbers. This is how I'm ...
0
votes
0answers
16 views

No simple closed form for Bell numbers

The Bell number $B_n$ is the number of partitions of $[n]$. Unlike other basic combinatorial quantities, $B_n$ has no simple finite closed form. This seems surprising to me. Can anyone explain why ...
3
votes
2answers
114 views

How many tuples of numbers from [1..n] have the sum of its elements equal to n?

[1..n] is the set of integers from 1 to n. The tuples can be of any finite length. The length of each tuple should range from 1 to n. I am asking how many tuples have elements such that the total sum ...
1
vote
2answers
34 views

Counting paths from the origin to a given point

Consider the following "walk" from the origin (0,0) in the plane to the point E=(5,5). A walk consists of starting at the origin and on each move, moving either one unit distance up or one unit ...
0
votes
0answers
18 views

Dependent Expectation in Random Numbers Illustrated by Prime Repetition in Pi

When approximating Pi, appending each numerical digit as you refine, what is the first repetition of a four-digit prime number? For instance the first repetition of any one-digit number in the ...
0
votes
1answer
19 views

On multiplicity representations of integer partitions of fixed length

This is a follow-up question on the question computing length of integer partitions and it is loosely related with the paper "On a partition identity". Let $\lambda$ be a partition of $n$, in the ...
3
votes
0answers
31 views

Counting the number of elements in a double coset

Let $G$ denote the groups of $n\times n$ invertible matrices and $H$ be the subgroup of invertible upper triangular matrices. For $n=2$, by row reduction, or equivalently LU decomposition, it is ...
0
votes
1answer
21 views

conjecture and prove set induction problem

Let $X_n$ = $\{1,2,3,4,\ldots,n\}$ (a set). Conjecture and prove that $\sum_{\emptyset \neq A\subseteq X_n}\frac{1}{p_A}=n$, where $p_A$ is the product of the subset. Attempt: $\sum_{\emptyset \neq ...
0
votes
1answer
21 views

Ordered sequences of integer with fixed sum

Let $I_S = \{0, 1, \ldots, S\}$, with $S \geq 1$. Consider all the ordered sequences of length $L \geq 2$ in $I_S^L$ such that the sum of all the terms is equal to $S$. Let $N(L,S)$ be the number of ...
0
votes
0answers
4 views

number of possible missmatches on a chain comparing with other

I have a question Find the number of mismatches that you can find comparing one chain to other Let's say "k" denotes the number of mismatches,"A" denotes the alphabeth that I can use, for example on ...
2
votes
0answers
42 views

Probability of at least m in a row out of n? (generic formula)

In a previously asked question of mine, I was specific in asking for a 75% freethrow shooter, what is the probability he would make at least 5 freethrow shots in a row out of 10. That means he would ...
0
votes
1answer
20 views

Is there a powerset equivalent to the Kleene star?

For some arbitrary alphabet E, is there an equivalent way to construct E* using powersets, sets, or sequences?
13
votes
1answer
146 views

Filling an $n\times n$ board

This problem has been bothering me for quite a while now. Consider an $n\times n$ chessboard, with $n$ being an odd positive integer. In the middle square of the board, a $0$ is placed. Starting with ...
1
vote
0answers
32 views

Count the strings with n0 K zeroes together

Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1. Now , the problem is we need to count the number of ways to fill these ...
11
votes
3answers
1k views

Is there a name for this kind of “Pascal's Triangle”?

I've been working on a problem and came across an interesting triangle that functions almost exactly like a Pascal Triangle. I'd like to see if I am able to find more about the properties of these ...
3
votes
1answer
23 views

Show by committee selection argument

First post in Stack Exchange and feel bad to be in need of help. But, I'm having a hard time understanding this one or rather showing the argument. $\binom{n}{k} = \binom{n-2}{k-2} + ...
0
votes
1answer
24 views

What is the combinatorial interpretation of the product of binomial coefficients?

Full disclosure: This question is relating to a homework question. It's not a homework question itself, but rather a clarifying question to help myself get a handle on the actual question. Suppose I ...
0
votes
0answers
42 views

Combinatorial Basics Question Regarding Guessing Subsets

Let $n = 10,000$. Suppose a friend tells you that he has a secret family of subsets of $\{1, 2, . . . , n\}$, and if you guess it correctly, he will give you one million dollars. You think you know ...
0
votes
0answers
29 views

Combinations - picking from groups of (different) identical items

First of all, I apologize if a similar question has been asked before. I did some searching and couldn't find anything here, but there might be an answer floating around somewhere. Basically, this ...
0
votes
3answers
39 views

How many sequences of $k$ elements in ascending order from a set $S$?

Suppose I have a set $S = \{1,2,\ldots,n\}$. How many sequence $r$ contains $k$ elements from set $S$ in ascending order if: $r$ contains repetition, i.e. an element in $S$ can appear several time ...
1
vote
1answer
33 views

Number of combinations of length

Basically I have a urn with balls in different colors. For example $urn = \{r, r, r, b, b, y\}$ How many different outputs (order matters) if I take 3 balls. The answer is $\#\{rrr, rrb, rry, rbr, ...
2
votes
2answers
33 views

The Number of Increasing Vectors $(x_1,…,x_k)$ Satisfying $1 \leq x_i \leq n$ and $x_1 < x_2 <…<x_k$

I want to find the number of increasing vectors $(x_1,...,x_k)$ satisfying $1 \leq x_i \leq n$ and $x_1 < x_2 <...<x_k$. Examples of vectors satisfying these conditions Let $n =5$ and ...
1
vote
1answer
18 views

Trying to prove that the poset of partitions ordered by refinement is a lattice

I am brand new to lattices/partitions. Given that the set of all partitions of a finite set is a poset ordered by refinement, how does one prove that it is a lattice? I know you have to prove that the ...
0
votes
1answer
34 views

computing length of integer partitions

This is a two-part question. (no pun intended) Part 1 I need to compute the length of each possible partition of an integer $n$. One possible way is to first compute all the partitions and the just ...
0
votes
0answers
18 views

Counting the exact number of sets in the Borel Field generated by a collection of “unrelated” sets

Prove: The B.F. generated by n given sets "without relations among them" has $2^{(2^n)}$ members. To be perfectly clear, "without relations among them" means that no set in the generating ...
0
votes
1answer
27 views

Giving a closed expression to $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i}$

I want to prove $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i} = \frac{(a-1)! b!}{(a+b)!}$ yet I feel like I don't know how to even approach this problem. Any hints are welcome.
1
vote
0answers
7 views

If there is a subset with sum divisible by n, then take out an integer of the subset. How many moves?

Fix an integer $n \ge 2$. A finite set $A \subset \mathbb{N} $ is given. Define $ s(X) = \sum_X x $, where $ X $ is a finite set. We know that $n \mid s(A)$. We can do just one move: if there is a ...
5
votes
5answers
105 views

Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $

I need any hint with calculating of the sum $$ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}. $$ Maple give the strange unsimplified result $$ I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( ...
0
votes
1answer
17 views

Number of sequences with n digits, even number of 1's (Continued question)

Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which ...
2
votes
1answer
41 views

The Number of Binary Vectors Whose Sum Is Greater Than $k$

I want to determine the number of vectors $(x_1,\ldots,x_n)$, such that each $x_i$ is either $0$ or $1$ and $$\sum\limits_{i=1}^n x_i \geq k$$ My Approach The number of $1$'s range from a minimum ...
-1
votes
0answers
38 views

Combinations of dots in a circle excluding neighbors [duplicate]

How many subsets with $k$ elements do $n$ dots put in the shape of a circle have, which do not include any neighbouring dots?
1
vote
2answers
34 views

A committee of four people, containing at least one man and one woman, must be chosen from four men and three women.

A committee of four people, containing at least one man and one woman, must be chosen from four men and three women. How many different committees are possible? I dont really now how to solve this. I ...
0
votes
3answers
49 views

Inclusion exclusion to solve $x_1+x_2+x_3=15$ with conditions

How to do this using inclusion/exclusion? Number of integers solutions to the equation $x_1+x_2+x_3=15$ with $x_1,x_2\leq 5$ and $x_3\leq 7$ for non negative integers $x_1,x_2,x_3$ I can do this ...
1
vote
3answers
32 views

How to find the total number of drinks possible

If I sold coffee in 4 sizes (small, medium, large, and extra large) and 4 varieties (Kenyan, Sumatran, Kona, and Columbian). Customers can choose to add one or more syrups that come in 5 flavors ...
0
votes
1answer
34 views

General Problems, Combinatorics. [on hold]

How many parallelograms can be found in a equilateral triangle of length 10 units divided equally into equilateral triangle of length 1 unit? Can anyone come up with a detailed solution?
-1
votes
3answers
85 views

Probabilities related to the sum of four dice

Suppose we have 4 fair six-sided dice of different colours and faces numbered 1,2,...,6 are rolled independently. (a) How many ways can a total of i. 4 ii. 5 iii. 6 be obtained? (b) Compute (to ...
1
vote
2answers
36 views

Generating function for number of integer solutions, no computer

How do you solve a Generating function for the number of integer solutions with no computer? Use a generating function to solve the number of integer solutions for $$x_1+x_2+x_3=17$$ Where ...
1
vote
0answers
19 views

Number of distinguishable arrangements of the word INDOOROOPILLY with three different conditions

I have the following three questions on a past final exam, I wanted to ask if I have done everything correctly. Thank you! How many distinguishable arrangements are there for the letters of the ...
1
vote
1answer
51 views

Question concerning a sequence in GAP

I would like to know, what's the best (fastest) way to programm the following in GAP (perhaps using some functionality from the QPA package): Input: $n\geq 2$ Output: A list of all sequences ...
0
votes
1answer
23 views

We are given a 15 bit string which must contain exactly 9 0's and 6 1's. Every 1 to be followed by a 0. # of possibilities to place the remaining 0s?

We are given a 15 bit string which must contain exactly 9 0's and 6 1's. Every 1 to be followed by a 0. # of possibilities to place the remaining 0s? I believe the answer is (3+7-1) choose 3 as I set ...
0
votes
0answers
34 views

Generating function to calculate number of ways of distributing $10$ or less items to $3$ people.

There is a container of 10 identical chocolate frogs and three students, Adam, Bob, and Charles, are to be given some of these chocolate frogs, but not necessarily all of the chocolate frogs. ...
0
votes
1answer
39 views

Counting in two ways

I've been having trouble proving the following equivalence. I suspect a two-way counting method is sufficient. Could anyone shed some light? $$\sum_{i=0}^{m}{ \binom{n-i}{m-i} \binom{k+i}{i}} ...
3
votes
0answers
44 views

Geometric Generating Functions

Let $p(t) = t^3 + Ft^2 + Et + V$, where $F,E,V$ are the number of faces, edges, and vertices of a cube, respectively. Factor $p(t)$ and explain your results in terms of generating functions. A hint ...
0
votes
1answer
35 views

How many elements does $\mathcal{P}(A)$ have?

Let $A$ be a set of size fifteen. Let $\mathcal{P}(A)$ denote the power set of $A$, that is the set of all the subsets of $A$. How many elements does $\mathcal{P}(A)$ contain? This is the same as ...
0
votes
1answer
46 views

Is there a binary [10,6,4] code?

Using the sphere padding packing bound formula I can conclude that 1 + 12 + 66 $\ge$ $2^{6}$ which indicates that there MAY be a binary [10,6,4] code, however I cannot prove that there is. How can I ...
0
votes
1answer
24 views

Sum of products of binomial coefficients is equal to another binomial coefficient [duplicate]

Need help in proving (by induction or by combinatorics) the following statement Is it possible to do it by induction? there are 3 veriables and I think I cannot easily do it by induction. Correct? ...
0
votes
1answer
38 views

Intuition behind $t(t+1)(t+2)\cdots(t+n-1)$

We have the following formula: Let $t$ be indeterminate and fix $n\geq 0$. Then \begin{equation} \sum_{k=0}^n c(n,k)t^k = t(t+1)(t+2)\cdots(t+n-1) \end{equation} where $c(n,k) = \#$ of permutations ...
0
votes
1answer
18 views

Paths in rectangular grid. Need some help with the logic behind it.

Suppose I have a an ixj grid (i rows, j columns) From the bottom left, to the top right, you may only move UP or RIGHT, how many paths are there from A to Z. In this case, you must go up twice, ...
2
votes
1answer
33 views

Combinatorial Analysis: Fermat's Combinatorial Identity

I was looking through practice questions and need some guidance/assistance in Fermat's combinatorial identity. I read through this on the stack exchange, but the question was modified in the latest ...
-3
votes
1answer
36 views

Alphabets Problem [on hold]

in the English alphabets of capital letters there are 15 stick letters which contain no curved lines, and 11 round letters which contain at least some curved segment. How many different 3 letters ...