For 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
3answers
133 views

Cardinality of a set $\{A,B\}$ $A$ is a subset of $B$, which is a subset of $S$

Let's say that $A$ is a subset of $B$ and be is a subset of a set $S$ of $n$ elements. How big is the set $\{(A,B)\}$ then.
2
votes
3answers
353 views

Prove that the combination formula can be reduced to…

Prove that: $$\frac{m!}{k!(m-k)!} = \frac{m}{k}\frac{m-1}{k-1}\cdots\frac{m-k+1}{1}$$ It's quite obvious when I write down some terms, but I just don't know how to make a rigorous proof. Any hints ...
7
votes
1answer
238 views

Probability that a $3\times 3$ matrix with entries in $\{0,1,2,3\}$ is invertible.

Let $A$ be a $3\times 3$ matrix, and each of its entries takes value from $\{0, 1, 2, 3\}$ with probability $1/4$ for each value. What is the probability that A is invertible? I have tried to list ...
2
votes
4answers
590 views

Permutation Theorem

I am reading about permutations, and came across this theorem, which has an accompanying proof. I was wondering if anyone knew of an example, that they could provide, when I would have to use the ...
5
votes
2answers
240 views

combinatorial descents finding the number of permutations with criteria

I need help with the following: Define a descent of a permutation to be $j$ when $p_{j+1} < p_j$. Then the descent set of a permutation is the set of all descents. For example, the ...
4
votes
3answers
153 views

In how many ways we can arrange two strings with distinct elements such that the order is intact?

In how many ways we can arrange two strings (with distinct elements) such that the order is intact? For example if the strings are , "aA" and "bk". The valid arrangements are: ...
1
vote
1answer
126 views

How to find (or 'generate') combinatorial meaning for the given expression

$\left(\dfrac{6(k-n)(k-1)}{(n-2)(n-1)}+1\right)\dfrac{30}{n(n+1)(n+2)}$ (for $n\geq 3$ and $1\leq k \leq n$) The expression comes from question Please help to find function for given inputs and ...
0
votes
1answer
139 views

Counting the number of possibilities

I have given number of y string variables. Assignments to these y variables can be done in only following: Right hand side of ...
1
vote
1answer
171 views

What is the probability for sequence of length $L$ in subset of $[n]$

I am trying to calculate the probability that I'll have a sequence of length $L$ in a random subset of $[n]$ when the subset size is $k$. For example, if $n=5$, $k=4$ and $L=2$ I'll have the ...
4
votes
1answer
59 views

Combinatorics of symmetric elements in $M_n(F_m)$

One of my tutees asked me a question about the number of such matrices, and I'm stumped: In the set of matrices of dimension $n\times n$ over a finite field $F_m$, we want to ask how many are ...
1
vote
1answer
99 views

Probability of two binomial trials of N tests with P=x having same outcome in 1<=Z<=N places.

As stated in title. I have an existing result (the target) of a binomial experiment of length N trials with P(success)=x. Is there an analytic/closed-form way of getting probability that a new trial ...
4
votes
2answers
2k views

Finding coefficient of generating function

Find the coefficient of $x^{52}$ in $$(x^{10} + x^{11} + \ldots + x^{25})(x + x^2 + \ldots + x^{15})(x^{20} + x^{21}+ \ldots + x^{45})$$ One thing I tried doing was factoring out $x^{10}, x, ...
1
vote
0answers
300 views

Constrained Permutation Problem

This isn't homework -- just a problem I came up with to test my skills. I failed, for now. A teacher must arrange $n$ students into a line, but $k$ pairs of the students cannot stand one ...
3
votes
3answers
414 views

Enumerating Rooted labeled trees without Lagrange inversion formula

I am wondering how to enumerate rooted labeled trees without the Langrange inversion formula. Because each tree is a collection of other trees, the recursive generating function becomes $$C(x) = x + ...
0
votes
1answer
63 views

Counting and set operations

Assuming I have items that each have an optional set of attributes. i.e. Item1[A], Item2[B], Item3[A,B], Item4[A,C], Item5[] And I have the count of each occurrence, i.e.: A = 3 (A has occurred 3 ...
1
vote
1answer
571 views

What is the minimum number of moves of solve the puzzle?

There is board in which there are $m\times m$ boxes each assigned an a non zero integer except one box which is marked as $0$ and is treated as vacant. Only the vertical and horizontal neighbors of ...
1
vote
0answers
69 views

combinatorial proof of Fibonacci identities [duplicate]

Give a combinatorial proof to each of the Fibonacci identities: $$nF_0+(n-1)F_1+\dots\dots+2F_{n-2}+F_{n-1}=F_{n+3}-(n+2)$$ and $$ F_2+F_5+\dots\dots+F_{3n+1}=\frac{F_{3n+1}-1}{2} $$ Assume that ...
0
votes
1answer
80 views

group theory - function into function

There is a group $A$ and it has $12$ elements, lets look at all the functions $A$ to $A$ which has the next trait: $a\in A, f(f(f(a)))=a$, but , $f(f(a))\neq a$. Prove its an Injective and ...
5
votes
1answer
76 views

Given $A$ and $B$, how many positive integers $N$ such that $N\times B$ has at least one divisior $D$ that lies in $N \lt D \le A$?

For two integers $A$ and $B$, how can we find the number of positive integers $N$ such that $N\times B$ has at least one divisior $D$ that lies in $N \lt D \le A$? For example, if $A = 100$ and $B = ...
15
votes
3answers
1k views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
0
votes
1answer
107 views

Finding a recurrence relation for the Josephus problem if we're looking at the person before the person who lives

Consider the Josephus problem. Let $L(n)$ be the number of the next to last person left standing. Find $L(12)$ and $L(13)$. Derive a recurrence for $L(n)$. I know that the Josephus problem is ...
1
vote
3answers
55 views

The elements in a recursive set

I have a set of numbers that is defined in the following way: $a_1 = \{1,-1\}$ $a_2 = \{2,0,0,-2\}$ $a_3 = \{3,1,1,-1,1,-1,-1,-3\}$ $a_n = \{a_{n-1} +1 , a_{n-1} -1 \}$ i.e. at each step we ...
1
vote
0answers
104 views

Probabilistic results on the elementary symmetric polynomials

The elementary symmetric polynomials of degree $k$ in $N$ variables are defined as $$e_k(x_1, \ldots, x_N) = \sum_{(i_1,\ldots,i_N) \in I_k^N}{x_1^{i_1}\ldots x_N^{i_N}}, \quad 0 \le k \le N$$ with ...
2
votes
1answer
192 views

Upper bound for ramsey number $r(a_1,\ldots, a_m)$

I am looking for any (finite) upper bound of the ramsey number $r(a_1,\ldots, a_m)$. I can prove the well known fact for any positive integers $a,b$ there is a $c$ for which $c\ge r(a,b)$ by taking ...
2
votes
1answer
237 views

Count the subsets of [n] whose sum is modulo $2^k$

Prove that for all $k \geq 1$ and $n \geq 2 ^{k-1}$, the number of subsets of $\{1,2,3\cdots n\}$ with sum congruent to $i$ mod $2^k$, equals the number with sum congruent to $i+1$ mod $2^k$, for all ...
1
vote
1answer
160 views

Elementary Generating Function Models

An international singing contest has $5$ distinct entrants from 50 different countries. Use a generating function for modeling the number of ways to pick $20$ semifinalists if there is at most $1$ ...
0
votes
1answer
330 views

how many combinations on a variable number of items?

I havent done combinations in forever, so I have no idea howto do this... I have an unknown quantity of items in a set, and I need to figure out how many combinations there are of 35 unique items ...
1
vote
1answer
150 views

A Combinatorial Question to Solve a System of Equations [duplicate]

Suppose we have $N$ integer-valued variables $i_1$, $i_2$, $\cdot\cdot\cdot$, $i_N$, such that each variable can take integer values from 0 to $k$, and the sum of these $N$ variables is also equal to ...
2
votes
1answer
164 views

applying multi-section formula to find convergence

The question asks to use the multi-section technique to determine if $$\sum_{n>=0} (a^n)/(4n +1)!$$ converges, and to provide a finite expression for the exact value of the series. The multi ...
1
vote
1answer
108 views

What is the bijection in this combinatorics example?

Example 3.19. A medical student has to work in a hospital for five days in January. However, he is not allowed to work two consecutive days in the hospital. In how many different ways can he ...
0
votes
1answer
60 views

Does $ \sum_{k = 0}^{\infty} \sum_{n = 0}^{\infty}\frac{B^k C^{(n+k+1)}}{(ib)^n k! (n+k+1)!}$ converge?

In relation to my question: Finding the residue of function with Laurent series $\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\frac{y^n(A+By+Cy{^-1})^k}{\beta (\beta i)^n \ k!}$ I need to find an expression ...
0
votes
0answers
51 views

Name for a type of combinatorial design?

Let $X$ be a ground set, and consider a collection $\mathscr{S}$ of subsets of $X$, $\mathscr{S} = \{S_1, \dots, S_n\}$. We would like to find a collection $\mathscr{S}'$ with the property that for ...
2
votes
3answers
6k views

probability selecting marbles

can someone solve this example? An urn contains 2 Red marbles, 3 White marbles and 4 Blue marbles. You reach in and draw out 3 marbles at random (without replacement). What is the probability that ...
0
votes
2answers
43 views

probability of events problem

need help with this problem, can someone walk me through how to do this problem Let A and B be events with P(A) = 3/7 ; P(B) = 1/2 and P((A U B)c) = 3/8. What is P(A ∩ B)?
2
votes
3answers
223 views

Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem?

Can this identity be derived from the binomial theorem? $$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$$ I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it ...
0
votes
1answer
97 views

probability of selecting dvds

studying for a test, cant figure out this probability problem A bin at Blockbuster contains 100 DVD's of which 20 are defective. You randomly select 10 and try them out at home. You discover that ...
2
votes
2answers
493 views

Pseudocode for view the combinations .

Can you help me please with a program which can calculate the number of combinations and to view it ? A pseudocode ? Is there something like a code - to program it ? thanks :)
1
vote
1answer
50 views

Controlling vote

Setting Suppose $n$ students plan to go $m$ tourist spots $s_1, \cdots, s_m$ together. But it turns out that the schedule is tight. So they decide to go $(m - 1)$ tourist spots instead. To determine ...
1
vote
1answer
130 views

Stirling numbers

Let $c \binom n k$ denote the number of permutations in $S_n$ with $k$ cycles. Find formulas for $c \binom n {n-2}$ and for $c \binom n 2$, and double-check that they hold for $n = 4$.
1
vote
1answer
301 views

The number of possible combination of column values

Sorry if this has been asked before, tried to look through older answers but don't get any of the formulas there and don't understand the questions asked either. I would like to calculate possible ...
0
votes
3answers
98 views

How many ways we can choose 15 people

A scientific research institue in the Czech Republic has $30$ members. Ten of them speak English, $8$ speak German, and $12$ speak Spanish. How many ways can choose $15$ people, including at least $2$ ...
1
vote
1answer
78 views

A combinatorial problem about distributing different kinds of balls to different people

Assume there are k kinds of balls. The number of the $i$-th kind of ball is $a_i$, thus there are $\sum_{i=1}^k a_i$ balls in total. The same kind of balls are identical. There are m different men. ...
3
votes
1answer
1k views

Determine the number of irreducible monic polynomials of degree 3 in $\mathbb F_p[x]$

Determine the number of irreducible monic polynomials of degree 3 in $\mathbb F_p[x]$ where $p$ is a prime. I'd like to start off by acknowledging that I know there are many posts relating to similar ...
0
votes
2answers
83 views

Error propagation through recurrence relation

I want to see how the error propagates on a mapping that I have. I have proven that $$|f(x+\varepsilon)-f(x)|=\varepsilon(1+\varepsilon),$$ let $\varepsilon_n$ be the error after $n$ applications of ...
9
votes
3answers
1k views

What are some measures of connectedness in graphs?

I am not a mathematician (I am an engineer who is working on improving his mathematics), so I apologize in advance if my question is trivial. Consider a graph of $N$ nodes, with some defined ...
4
votes
3answers
2k views

prove $n$-cube is bipartite

prove $n$-cube is a bipartite graph for all $n\ge1$ This is a problem in my textbook and I cannot figure it out at all and have a test on graph theory tomorrow any help would be appreciated since I ...
2
votes
2answers
176 views

Combination / Permutation Question

There are 3 bags and 5 different marbles. In how many ways can the marbles be put into the bags? (disclosure - the question is one of many in a teacher prep study guide. I am taking the ...
1
vote
2answers
92 views

Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
0
votes
3answers
8k views

How many odd numbers with distinct digits between 1000 and 9999

How many numbers with distinct digits are there between 1000 and 9999. [1] I came up with a solution like this. Since we can't know what numbers have been used, in the tens, hundreds and thousands ...